package org.chnxi.datastructures.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分法查找
 * 该数组必须是有序的
 */
public class BinarySearching {

    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};

        int resultIdx = binarySearch(arr , 0 , arr.length , 1);

        if(resultIdx == -1){
            System.out.println("未找到");
        }else{
            System.out.println("索引位置："+resultIdx);
        }

        System.out.println("查找数组中所有符合规则的数值：");
        int[] arr2 = {1,8,10,89,1000,1000,1000,1234};

        List<Integer> result = binarySearchAll(arr2 , 0 , arr2.length , 1000);
        System.out.println("符合条件的索引位个数："+result.size());
        for (int i = 0; i < result.size(); i++){
            System.out.println("第"+i+"位上的索引："+result.get(i));
        }

    }

    /**
     * 查找单个
     * @param arr 数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 要查找的值
     * @return 找到就返回索引值，未找到返回-1
     */
    public static int binarySearch(int[] arr , int left , int right , int findVal){

        //未找到退出递归
        if(left > right){
            return -1;
        }

        //找到中间索引
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal){
            return binarySearch(arr , mid + 1 , right , findVal);
        }else if(findVal < midVal){
            return binarySearch(arr , left , mid -1 , findVal);
        }else{
            return mid;
        }
    }


    /**
     * {1,8,10,89,1000,1000,1234}
     * 找到所有符合规则的索引位置
     * @param arr 数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 要查找的值
     * @return 返回所有找到的索引
     */
    public static List<Integer> binarySearchAll(int[] arr , int left , int right , int findVal){

        //未找到退出递归
        if(left > right){
            return new ArrayList<>();
        }

        //找到中间索引
        int mid = (left + right) / 2;
        System.out.println("left="+left+";right="+right+";mid="+mid);
        int midVal = arr[mid];

        if(findVal > midVal){
            return binarySearchAll(arr , mid + 1 , right , findVal);
        }else if(findVal < midVal){
            return binarySearchAll(arr , left , mid -1 , findVal);
        }else{
            List<Integer> list = new ArrayList<Integer>();
            //先将找到的中间位放入结果
            list.add(mid);

            //向左依次查找是否匹配，tmp<0，表示已找到最左端
            int tmp = mid -1;
            while(true){
                if(tmp < 0 || arr[tmp] != findVal){
                    break;
                }
                list.add(tmp);
                tmp -=1;
            }

            //向右依次查找是否匹配，tmp>arr.length-1，表示已找到最右端
            tmp = mid + 1;
            while(true){
                if(tmp > arr.length -1 || arr[tmp] != findVal){
                    break;
                }
                list.add(tmp);
                tmp +=1;
            }

            return list;
        }
    }


}
